// script.js
document.addEventListener('DOMContentLoaded', () => {
    const arrayContainer = document.getElementById('array-container');
    const startBtn = document.getElementById('start-btn');
    const resetBtn = document.getElementById('reset-btn');
    const algorithmSelect = document.getElementById('algorithm-select');
    let array = generateRandomArray(15); // 初始数组

    // 生成随机数组
    function generateRandomArray(size) {
        return Array.from({ length: size }, () => Math.floor(Math.random() * 100) + 1);
    }

    // 渲染数组
    function renderArray(arr, highlightedIndices = [], sortedIndices = []) {
        arrayContainer.innerHTML = '';
        const maxHeight = Math.max(...arr); // 获取最大值用于比例计算
        arr.forEach((value, index) => {
            const element = document.createElement('div');
            element.className = 'array-element';
            element.textContent = value;
            element.style.height = `${(value / maxHeight) * 100}%`; // 高度与数值成正比
            if (highlightedIndices.includes(index)) {
                element.style.backgroundColor = '#FF0000'; // 高亮当前操作的元素
            }
            if (sortedIndices.includes(index)) {
                element.classList.add('sorted'); // 标记已排序的元素
            }
            arrayContainer.appendChild(element);
        });
    }

    // 交换数组元素
    function swap(arr, i, j) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 延迟函数
    function sleep(ms) {
        return new Promise(resolve => setTimeout(resolve, ms));
    }

    // 冒泡排序
    async function bubbleSort(arr) {
        const len = arr.length;
        for (let i = 0; i < len; i++) {
            for (let j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    renderArray(arr, [j, j + 1], Array.from({ length: i }, (_, k) => len - 1 - k));
                    await sleep(200);
                }
            }
        }
        renderArray(arr, [], Array.from({ length: len }, (_, i) => i)); // 全部标记为已排序
    }

    // 选择排序
    async function selectionSort(arr) {
        const len = arr.length;
        for (let i = 0; i < len; i++) {
            let minIndex = i;
            for (let j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex !== i) {
                swap(arr, i, minIndex);
                renderArray(arr, [i, minIndex], Array.from({ length: i }, (_, k) => k));
                await sleep(200);
            }
        }
        renderArray(arr, [], Array.from({ length: len }, (_, i) => i)); // 全部标记为已排序
    }

    // 插入排序
    async function insertionSort(arr) {
        const len = arr.length;
        for (let i = 1; i < len; i++) {
            let j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
                renderArray(arr, [j, j - 1], Array.from({ length: i }, (_, k) => k));
                await sleep(200);
                j--;
            }
        }
        renderArray(arr, [], Array.from({ length: len }, (_, i) => i)); // 全部标记为已排序
    }

    // 归并排序
    async function mergeSort(arr) {
        async function merge(left, right) {
            let result = [];
            while (left.length && right.length) {
                if (left[0] < right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
                renderArray([...result, ...left, ...right]);
                await sleep(200);
            }
            return [...result, ...left, ...right];
        }

        async function sort(arr) {
            if (arr.length <= 1) return arr;
            const mid = Math.floor(arr.length / 2);
            const left = await sort(arr.slice(0, mid));
            const right = await sort(arr.slice(mid));
            return await merge(left, right);
        }

        array = await sort(arr);
        renderArray(array, [], Array.from({ length: array.length }, (_, i) => i)); // 全部标记为已排序
    }

    // 快速排序
    async function quickSort(arr, low = 0, high = arr.length - 1) {
        if (low < high) {
            const pivotIndex = await partition(arr, low, high);
            await quickSort(arr, low, pivotIndex - 1);
            await quickSort(arr, pivotIndex + 1, high);
        }
        renderArray(arr, [], Array.from({ length: arr.length }, (_, i) => i)); // 全部标记为已排序
    }

    async function partition(arr, low, high) {
        const pivot = arr[high];
        let i = low - 1;
        for (let j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
                renderArray(arr, [i, j]);
                await sleep(200);
            }
        }
        swap(arr, i + 1, high);
        renderArray(arr, [i + 1, high]);
        await sleep(200);
        return i + 1;
    }

    // 堆排序
    async function heapSort(arr) {
        const len = arr.length;
        for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
            await heapify(arr, len, i);
        }
        for (let i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            renderArray(arr, [0, i], Array.from({ length: len - i }, (_, k) => i + k));
            await sleep(200);
            await heapify(arr, i, 0);
        }
        renderArray(arr, [], Array.from({ length: len }, (_, i) => i)); // 全部标记为已排序
    }

    async function heapify(arr, len, i) {
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest !== i) {
            swap(arr, i, largest);
            renderArray(arr, [i, largest]);
            await sleep(200);
            await heapify(arr, len, largest);
        }
    }

    // 希尔排序
    async function shellSort(arr) {
        const len = arr.length;
        let gap = Math.floor(len / 2);
        while (gap > 0) {
            for (let i = gap; i < len; i++) {
                let j = i;
                while (j >= gap && arr[j] < arr[j - gap]) {
                    swap(arr, j, j - gap);
                    renderArray(arr, [j, j - gap]);
                    await sleep(200);
                    j -= gap;
                }
            }
            gap = Math.floor(gap / 2);
        }
        renderArray(arr, [], Array.from({ length: len }, (_, i) => i)); // 全部标记为已排序
    }

    // 计数排序
    async function countingSort(arr) {
        const max = Math.max(...arr);
        const count = Array(max + 1).fill(0);
        for (let num of arr) {
            count[num]++;
        }
        let index = 0;
        for (let i = 0; i <= max; i++) {
            while (count[i] > 0) {
                arr[index] = i;
                count[i]--;
                index++;
                renderArray(arr);
                await sleep(200);
            }
        }
        renderArray(arr, [], Array.from({ length: arr.length }, (_, i) => i)); // 全部标记为已排序
    }

    // 基数排序
    async function radixSort(arr) {
        const max = Math.max(...arr);
        const maxDigits = String(max).length;
        for (let i = 0; i < maxDigits; i++) {
            const buckets = Array.from({ length: 10 }, () => []);
            for (let num of arr) {
                const digit = getDigit(num, i);
                buckets[digit].push(num);
            }
            arr = [].concat(...buckets);
            renderArray(arr);
            await sleep(200);
        }
        renderArray(arr, [], Array.from({ length: arr.length }, (_, i) => i)); // 全部标记为已排序
    }

    function getDigit(num, place) {
        return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
    }

    // 桶排序
    async function bucketSort(arr) {
        const bucketSize = 10;
        const max = Math.max(...arr);
        const min = Math.min(...arr);
        const bucketCount = Math.floor((max - min) / bucketSize) + 1;
        const buckets = Array.from({ length: bucketCount }, () => []);
        for (let num of arr) {
            const index = Math.floor((num - min) / bucketSize);
            buckets[index].push(num);
        }
        arr = [];
        for (let bucket of buckets) {
            bucket.sort((a, b) => a - b);
            arr = arr.concat(bucket);
            renderArray(arr);
            await sleep(200);
        }
        renderArray(arr, [], Array.from({ length: arr.length }, (_, i) => i)); // 全部标记为已排序
    }

    // 事件监听
    startBtn.addEventListener('click', async () => {
        const algorithm = algorithmSelect.value;
        switch (algorithm) {
            case 'bubbleSort':
                await bubbleSort(array);
                break;
            case 'selectionSort':
                await selectionSort(array);
                break;
            case 'insertionSort':
                await insertionSort(array);
                break;
            case 'mergeSort':
                await mergeSort(array);
                break;
            case 'quickSort':
                await quickSort(array);
                break;
            case 'heapSort':
                await heapSort(array);
                break;
            case 'shellSort':
                await shellSort(array);
                break;
            case 'countingSort':
                await countingSort(array);
                break;
            case 'radixSort':
                await radixSort(array);
                break;
            case 'bucketSort':
                await bucketSort(array);
                break;
        }
    });

    resetBtn.addEventListener('click', () => {
        array = generateRandomArray(15);
        renderArray(array);
    });

    // 初始化渲染
    renderArray(array);
});